package com.berchen.offer;

import com.berchen.test.ListNode;

/**
 * 1 4 3 2 5 2 传值3
 * 得到数据 1 2 2 4 3 5
 * 将链表中小于3 的值放到 大于等于3 的数据前面
 */
public class Test19 {
    public ListNode partition(ListNode head, int x) {

        if(head==null){
            return head;
        }
        ListNode min=null,minTemp=null;
        ListNode max=null,maxTemp=null;
        ListNode temp=head;

        while (temp!=null){
            if(temp.val<x){
                if(min==null){
                    min=temp;
                    minTemp=min;
                    temp=temp.next;
                    min.next=null;
                    minTemp.next=null;
                }else {
                    minTemp.next=temp;
                    minTemp=minTemp.next;
                    temp=temp.next;
                    minTemp.next=null;
                }
            }else {
                if(max==null){
                    max=temp;
                    maxTemp=max;
                    temp=temp.next;
                    max.next=null;
                    maxTemp.next=null;
                }else {
                    maxTemp.next=temp;
                    maxTemp=maxTemp.next;
                    temp=temp.next;
                    maxTemp.next=null;
                }
            }

        }
        if(minTemp==null){
            return max;
        }else {

            minTemp.next = max;
            return min;
        }
    }
}
